SCOI2016美味

发表于
字数统计: 902字 | 阅读时长 ≈ 5min

[SCOI2016]美味

问题描述

一家餐厅有 n 道菜，编号 1…n ，大家对第 i 道菜的评价值为 ai(1≤i≤n)。有 m 位顾客，第 i 位顾客的期望值为 bi，而他的偏好值为 xi 。因此，第 i 位顾客认为第 j 道菜的美味度为 bi XOR (aj+xi)，XOR 表示异或运算。第 i 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第 li 道到第 ri 道中选择。请你帮助他们找出最美味的菜。

输入格式

第1行，两个整数，n，m，表示菜品数和顾客数。

第2行，n个整数，a1，a2，…，an，表示每道菜的评价值。

第3至m+2行，每行4个整数，b，x，l，r，表示该位顾客的期望值，偏好值，和可以选择菜品区间。

输出格式

输出m 行，每行一个整数表示该位顾客选择的最美味的菜的美味值。

样例输入

4 4
1 2 3 4
1 4 1 4
2 3 2 3
3 2 3 3
4 1 2 4

样例输出

9
7
6
7

提示

1≤n≤2×10^5,
0≤ai,bi,xi<10^5,
1≤li≤ri≤n(1≤i≤m),
1≤m≤10^5

如果不加上$a_j$，那么就是可持久化trie裸题。

加上$a_j$之后仍然考虑按位贪心。判断某一位能不能取1，就是判断区间里是否存在大小在某个范围内的数，这个采用主席树可以$O(logn)$判断，时间复杂度$O(nlog^2n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define MAXN 200005
#define MAXT 10000005
using namespace std;

char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R(){
	char s=GC;int sign=0,v=0;
	while((s!='-')&&(s>57||s<48))s=GC;
	if(s=='-')s=GC,sign=1;
	for(;s>47&&s<58;s=GC)v=v*10+s-48;
	return sign?-v:v;
}

int N,M,A[MAXN],Ans;

int tot,rt[MAXN],ls[MAXT],rs[MAXT],sum[MAXT];
int Build(int l,int r){
	int mid=l+r>>1,p=++tot;
	if(l==r)return p;
	ls[p]=Build(l,mid);
	rs[p]=Build(mid+1,r);
	return p;
}

int Copy(int p){
	int cp=++tot;
	ls[cp]=ls[p];rs[cp]=rs[p];sum[cp]=sum[p];
	return cp;
}

int Modify(int p,int l,int r,int k){
	int mid=l+r>>1,cp=Copy(p);
	sum[cp]++;
	if(l==r)return cp;
	if(k<=mid)ls[cp]=Modify(ls[p],l,mid,k);
	else rs[cp]=Modify(rs[p],mid+1,r,k);
	return cp;
}

int GetSum(int u,int v,int l,int r,int x,int y){
	int mid=l+r>>1,ret=0;
	if(x<=l&&r<=y)return sum[u]-sum[v];
	if(x<=mid)ret+=GetSum(ls[u],ls[v],l,mid,x,y);
	if(y>mid)ret+=GetSum(rs[u],rs[v],mid+1,r,x,y);
	return ret;
}

int main(){
	int i,j,b,x,l,r,qry,L,R,tmp;
	N=_R();M=_R();
	for(i=1;i<=N;i++)A[i]=_R();

	rt[0]=Build(1,300000);
	for(i=1;i<=N;i++)rt[i]=Modify(rt[i-1],1,300000,A[i]+1);

	for(i=1;i<=M;i++){
		b=_R();x=_R();l=_R();r=_R();
		Ans=0;tmp=0;
		for(j=17;j>=0;j--){
			if(b>>j&1){
				L=0;R=(1<<j)-1;
				L+=tmp-x;R+=tmp-x;
				if(R<0)continue;
				L=max(0,L);
				if(GetSum(rt[r],rt[l-1],1,300000,L+1,R+1))Ans|=(1<<j);
				else tmp|=(1<<j);
			}
			else{
				L=1<<j;R=(1<<j+1)-1;
				L+=tmp-x;R+=tmp-x;
				if(R<0)continue;
				L=max(0,L);
				if(GetSum(rt[r],rt[l-1],1,300000,L+1,R+1))Ans|=(1<<j),tmp|=(1<<j);
			}
		}
		printf("%d\n",Ans);
	}
}